package com.practice.niuke.new_direct_basics.class04;

import java.util.Stack;

/**
 * 判断一个链表是否为回文结构
 *
 * 【题目】 给定一个单链表的头节点head， 请判断该链表是否为回文结构。
 * 【例子】 1->2->1， 返回true； 1->2->2->1， 返回true； 15->6->15， 返回true；
 *  1->2->3， 返回false。
 * 【例子】 如果链表长度为N， 时间复杂度达到O(N)， 额外空间复杂度达到O(1)。
 */
public class Code04_IsPalindromeList {

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 方法一：使用一个栈结构
	 * （1）遍历一遍链表，将链表的各个节点入栈。
	 * （2）在遍历一遍链表，每遍历一个节点，就在栈中弹出一个元素，两者进行比较。
	 *  need n extra space
	 *
	 * @param head 单链表头结点
	 * @return boolean
	 */
	public static boolean isPalindrome1(Node head) {
		Stack<Node> stack = new Stack<Node>();
		Node cur = head;
		while (cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
		while (head != null) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	/**
	 * 方法：快慢指针+栈
	 * need n/2 extra space
	 *
	 * @param head 单链表头结点
	 * @return boolean
	 */
	public static boolean isPalindrome2(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		//-------------------快慢指针找到链表中间位置（上中位处）-----
		Node right = head.next;
		Node cur = head;
		while (cur.next != null && cur.next.next != null) {
			right = right.next;
			cur = cur.next.next;
		}
		//-------------------将链表右部分入栈-------------------------
		Stack<Node> stack = new Stack<Node>();
		while (right != null) {
			stack.push(right);
			right = right.next;
		}
		//---从表头到中间位置遍历链表、分别与栈中的元素比较------------
		while (!stack.isEmpty()) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

	/**
	 * 方法：快慢指针+右半部分逆序
	 * need O(1) extra space
	 *
	 * @param head 单链表头结点
	 * @return boolean
	 */
	public static boolean isPalindrome3(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		//-------------------快慢指针找到链表中间位置（上中位处）-----
		// n1开始当做“慢指针”使用
		Node n1 = head;
		// n2开始当做“快指针”使用
		Node n2 = head;
		// find mid node
		while (n2.next != null && n2.next.next != null) {
			// n1 -> mid
			n1 = n1.next;
			// n2 -> end
			n2 = n2.next.next;
		}
		//-------------------右半部分逆序----------------------------
		// n2 -> right part first node
		n2 = n1.next;
		// mid.next -> null
		n1.next = null;
		Node n3 = null;
		// right part convert （右半部分逆序）
		while (n2 != null) {
			// n3 -> save next node
			n3 = n2.next;
			// next of right node convert
			n2.next = n1;
			// n1 move
			n1 = n2;
			// n2 move
			n2 = n3;
			/**
			 * Node next = n2.next;
			 * n2.next = n3;
			 * n3 = n2;
			 * n2 = next;
			 */
		}
		//---------------------首（左）、尾（右）指针遍历链表进行比较------------------
		n3 = n1; // n3 -> save last node （尾/右指针）
		n2 = head;// n2 -> left first node （首/左指针）
		boolean res = true;
		// check palindrome 比较 首、尾指针处 所指向元素
		while (n1 != null && n2 != null) {
			if (n1.value != n2.value) {
				res = false;
				break;
			}
			// left to mid
			n1 = n1.next;
			// right to mid
			n2 = n2.next;
		}
		//-------------------右半部分再次逆序（还原）------------------------
		n1 = n3.next;
		n3.next = null;
		while (n1 != null) { // recover list
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}

	public static void printLinkedList(Node node) {
		System.out.print("Linked List: ");
		while (node != null) {
			System.out.print(node.value + " ");
			node = node.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {

		Node head = null;
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(2);
		head.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

		head = new Node(1);
		head.next = new Node(2);
		head.next.next = new Node(3);
		head.next.next.next = new Node(2);
		head.next.next.next.next = new Node(1);
		printLinkedList(head);
		System.out.print(isPalindrome1(head) + " | ");
		System.out.print(isPalindrome2(head) + " | ");
		System.out.println(isPalindrome3(head) + " | ");
		printLinkedList(head);
		System.out.println("=========================");

	}

}
